'''
    不借助第三个变量交换两个数
    方法一：
        a=a+b
        b=a-b
        a=a-b
    方法二：
        a=a-b
        b=b+a
        a=b-a
    方法三：
        a=b-a
        b=b-a
        a=b+a
    方法四：
        a=a^b
        b=a^b
        a=a^b
'''

'''
    1.冒泡排序
'''
def bubbleSort(nums):
    L=len(nums)
    for i in range(1,L):
        for j in range(0,L-i):
            if nums[j]>nums[j+1]:
                tmp=nums[j+1]
                nums[j+1]=nums[j]
                nums[j]=tmp    
    return nums

'''
    2.选择排序
'''
def selectSort(nums):
    L=len(nums)
    i=0
    while i<=L-1:
        j=i
        min=nums[i]
        min_id=i
        while j<=L-1:
            if nums[j]<min:
                min=nums[j]
                min_id=j
            j=j+1
        tmp=nums[i]
        nums[i]=nums[min_id]
        nums[min_id]=tmp
        i=i+1
    return nums

'''
    3.插入排序
'''
def insertSort(nums):
    L=len(nums)
    for i in range(1,L):
        j=i
        while (nums[j]<nums[j-1])&(j>0):
            nums[j]=nums[j]^nums[j-1]
            nums[j-1]=nums[j]^nums[j-1]
            nums[j]=nums[j]^nums[j-1]
            j=j-1
    return nums

def insertSort_2(nums):
    res=[nums[0]]
    for i in range(1,len(nums)):
        j=len(res)-1
        while (nums[i]<res[j])&(j>=0):
            j=j-1
        res.insert(j+1,nums[i])  
    return res

'''
    4.希尔排序 选择希尔增量(L/2,L/4,L/8,...1)
'''
def shellSort(nums):
    L=len(nums)
    gap=L>>1    #增量初始化为L/2
    while gap>=1:   #增量的边界条件gap>=1
        for i in range(gap):    #将数组分为gap个子数组，这些子数组的第一个数分别为1,2,...,gap-1
            # 对每个子序列进行插入排序
            j=i     # j代表数组前面已排列部分的最后一个元素，初始值为子数组的第一个元素
            while j < L-gap:    # 边界条件为j<L-gap，保证下一行不会出现数组越界
                k=j+gap     # k代表数组未排序部分的迭代变量，初始值为未排列部分的第一个元素(j+gap)
                while (nums[k]<nums[k-gap])&(k>=gap):   
                    '''
                        边界条件 nums[k]>=nums[k-gap] 或者 k<=gap 退出循环
                        如果nums[k]<nums[k-gap]，交换nums[k]和nums[k-gap]
                    '''
                    nums[k]=nums[k]^nums[k-gap]
                    nums[k-gap]=nums[k]^nums[k-gap]
                    nums[k]=nums[k]^nums[k-gap]
                    k=k-gap
                j=j+gap
        gap=gap>>1
    return nums

'''
    5.归并排序
'''
def mergeSort(nums,start,end):
    if start>=end:
        return nums
    
    mid=(start+end)>>1

    nums=mergeSort(nums,start,mid)
    nums=mergeSort(nums,mid+1,end)

    nums=merge(nums,start,mid,end)

    return nums

def merge(nums,start,mid,end):
    tmp=[]
    i=start
    j=mid+1
    while (i<=mid) & (j<=end):
        if nums[i]<nums[j]:
            tmp.append(nums[i])
            i=i+1
        else:
            tmp.append(nums[j])
            j=j+1 
        
    if i==mid+1:
        while j<=end:
            tmp.append(nums[j])
            j=j+1
    if j==end+1:
        while i<=mid:
            tmp.append(nums[i])
            i=i+1
    
    for i in range(start,end+1):
        nums[i]=tmp[i-start]

    return nums

'''
    6.堆排序
    参考：https://zhuanlan.zhihu.com/p/346488612
'''
def max_heap_down(nums,start,end):
    c=start
    l=2*c+1

    while l<=end:
        if (l<end)&(nums[i]<nums[i+1]):
            l=l+1
        if nums[c] > nums[l]:
            break
        else:
            nums[c]=nums[c]^nums[l]
            nums[l]=nums[c]^nums[l]
            nums[c]=nums[c]^nums[l]
        c=l
        l=2*l+1

    return nums

def heapSort(nums):
    L=len(nums)

    i=(L>>1)-1  #取最后一个非叶子节点
    while i>=0:
        nums=max_heap_down(nums,i,L-1)
        i=i-1
    
    i=L-1
    while i>0:
        nums[0]=nums[0]^nums[i]
        nums[i]=nums[0]^nums[i]
        nums[0]=nums[0]^nums[i]
        nums=max_heap_down(nums,0,i-1)
        i=i-1
    
    return nums

'''
    7.计数排序
    参考：https://zhuanlan.zhihu.com/p/137576551
'''
def countSort(nums):
    L=len(nums)
    max=nums[0]
    min=nums[0]

    i=0
    while i<L:
        if max<nums[i]:
            max=nums[i]
        if min>nums[i]:
            min=nums[i]
        i=i+1

    length=max-min+1
    list=[0]*length

    for i in range(L):
        list[nums[i]-min]=list[nums[i]-min]+1

    res=[]
    for i in range(length):
        for j in range(list[i]):
            res.append(i+min)

    return res

'''
    8.快速排序
'''
def quickSortPartition(nums,l,r):
    key=nums[l]
    while l<r:
        while (l<r)&(nums[r]>=key):
            r=r-1
        if l<r:
            nums[l]=nums[r]
        while (l<r)&(nums[l]<key):
            l=l+1
        if l<r:
            nums[r]=nums[l]
    nums[l]=key
    return l

def quickSort(nums,l,r):
    if l>=r:
        return nums
    i=quickSortPartition(nums,l,r) 
    nums=quickSort(nums,l,i-1)
    nums=quickSort(nums,l+1,r)
    return nums

'''
    9.基数排序
'''
def sort(nums,b):
    list=[]
    L=len(nums)
    for id in range(L):
        key=nums[id]
        i=b
        while i>0:
            key=key//10
            i=i-1
        list.append([key,nums[id]])

    for i in range(1,L-1):
        for j in range(0,L-i):
            if list[j][0]>list[j+1][0]:
                tmp=list[j]
                list[j]=list[j+1]
                list[j+1]=tmp
    
    for i in range(L):
        nums[i]=list[i][1]

    return nums

def radixSort(nums):
    L=len(nums)

    max=nums[0]
    for i in range(1,L):
        if max<nums[i]:
             max=nums[i]
    
    b=0
    while max!=0:
        max=max//10
        b=b+1

    for i in range(b):
        nums=sort(nums,i)

    return nums

def main():
    nums=[1,13,125,8,1,2,4,7,9]
    print(radixSort(nums))
    
if __name__=="__main__":
    main()